package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description: 整数拆分
 * 343 integer-break
 * @author: Zhang Bo
 * @create: 2022-04-13 11:13:52
 **/
public class IntegerBreak {
    public static void main(String[] args) {
        Solution solution = new IntegerBreak().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 用 3 去拆分就好了
         * @param n
         * @return
         */
        public int integerBreak(int n) {

            if (n == 2) {
                return 1;
            }
            if (n == 3) {
                return 2;
            }
            int count = 1;
            while (n > 4) {
                count *= 3;
                n -= 3;
            }
            while (n > 3) {
                count *= 2;
                n -= 2;
            }
            return count * n;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}